Permutations
$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\delim\{{#1}\}} \gdef\ceil#1{\delim\lceil{#1}\rceil} \gdef\unit#1{\ \text{#1}} $$
$n!$
From CB22:
The challenge is to construct a data structure for storing a permutation that takes less space than the trivial data structure, specifically 1.44 n fewer bits, while retaining the ability to quickly evaluate the permutation.
Take a permutation over $2^{32}$ elements. This can be represented as a vector of $2^{32}$ $32$-bit integers, taking $17.2\unit{GB}$. In theory it can be stored in
$$ \ceil{\log_{256} 2^{32}! } = 16.4 \unit{GB} $$
We can do better if we build an approximate lookup that returns a set of $n$ elements, one of which is the permutation. Split the permutation in blocks of size $n$. If we ignore the order within the blocks, they can be stored in $\ceil{\log_{256} {2^{32} \choose n} }$ bytes. If we pick a blocksize of $1427$ we get $4096\unit{B}$, a disk block.
